package com.sunny.example.dynamicschedule;

import java.util.Scanner;

/**
 * 购物单 HJ16
 */
public class DS2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int money, n = 0;
            money = scanner.nextInt();
            n = scanner.nextInt();
            Goods[] goods = new Goods[n + 1];
            int len = goods.length;
            for (int i = 1; i <= n; i++) {
                int v = scanner.nextInt();
                int p = scanner.nextInt();
                int q = scanner.nextInt();
                Goods g = new Goods();
                g.v = v;
                g.p = p;
                g.q = q;
                goods[i] = g;

            }

            for (int k = 1; k <= n; k++) {
                Goods gs = goods[k];
                int q = gs.q;
                if (q == 0) {
                    goods[k].isMain = true;
                }
                if (q > 0) {
                    //为附件时，需要与主件关联
                    if (goods[q].a1 == 0) {//附件1
                        goods[q].a1 = k;
                    }
                    if (goods[q].a2 == 0) {
                        goods[q].a2 = k;//附件2
                    }
                }
            }

            int[][] dp = new int[n + 1][money + 1];
            //存在4种状态
            //1、只买主件
            //2、买主件+附件1
            //3、买主件+附件2
            //4、买主件+附件1+附件2
            for (int i = 1; i <= n; i++) {//遍历横向
                int v, v1 = 0, v2 = 0, v3 = 0, tempDp, tempDp1 = 0, tempDp2 = 0, tempDp3 = 0;
                v = goods[i].v;//当前价钱
                tempDp = goods[i].p * v;//只有主件时

                //主件+附件1
                int index1 = goods[i].a1;
                if (index1 != 0) {
                    v1 = goods[index1].v + v;
                    tempDp1 = goods[index1].v * goods[index1].p + tempDp;
                }

                //主件+附件2
                int index2 = goods[i].a2;
                if (index2 != 0) {
                    v2 = goods[index2].v + v;
                    tempDp2 = goods[index2].v * goods[index2].p + tempDp;
                }

                //主件+附件1+附件2
                if (index1 != 0 && index2 != 0) {
                    v3 = goods[index1].v + goods[index2].v + v;
                    tempDp3 = goods[index1].v * goods[index1].p + goods[index2].v * goods[index2].p + tempDp;
                }

                for (int j = 1; j <= money; j++) {
                    //遍历纵向
                    if (goods[i].q > 0) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j];
                        if (j >= v && v != 0) {//状态1切换
                            //通用公式：cell[i][j] = Math.max((cell[i-1][j],(当前商品的价值 + (cell[i-1][j - 当前商品的重量]))))
                            dp[i][j] = Math.max(dp[i][j], tempDp + dp[i - 1][j - v]);
                        }
                        if (j >= v1 && v1 != 0) {//状态2切换
                            dp[i][j] = Math.max(dp[i][j], tempDp1 + dp[i - 1][j - v1]);
                        }

                        if (j >= v2 && v2 != 0) {//状态3切换
                            dp[i][j] = Math.max(dp[i][j], tempDp2 + dp[i - 1][j - v2]);
                        }
                        if (j >= v3 && v3 != 0) {//状态4切换
                            dp[i][j] = Math.max(dp[i][j], tempDp3 + dp[i - 1][j - v3]);
                        }
                    }

                }
            }


            System.out.println(dp[n][money]);


        }
    }

    public static class Goods {
        int v;//物品价格
        int p;//物品重要程度
        int q;//附件所属主件的编号

        boolean isMain; //标识是否为主件

        int a1 = 0;//附件1
        int a2 = 0;//附件2

    }
}
